11590 - Prefix lookup/11590.2.cpp

   1 //TLE
   2 using namespace std;
   3 #include <algorithm>
   4 #include <iostream>
   5 #include <iterator>
   6 #include <sstream>
   7 #include <fstream>
   8 #include <cassert>
   9 #include <climits>
  10 #include <cstdlib>
  11 #include <cstring>
  12 #include <string>
  13 #include <cstdio>
  14 #include <vector>
  15 #include <cmath>
  16 #include <queue>
  17 #include <deque>
  18 #include <stack>
  19 #include <list>
  20 #include <map>
  21 #include <set>
  22
  23 template <class T> string toStr(const T &x){ stringstream s; s << x; return s.str(); }
  24 template <class T> int toInt(const T &x){ stringstream s; s << x; int r; s >> r; return r; }
  25
  26 #define For(i, a, b) for (int i=(a); i<(b); ++i)
  27 #define foreach(x, v) for (typeof (v).begin() x = (v).begin(); x != (v).end(); ++x)
  28 #define D(x) cout << #x " is " << x << endl
  29
  30 typedef unsigned long long Int;
  31 const int BUFSIZE = 128;
  32 char buf[BUFSIZE];
  33
  34 int M;
  35 map<string, Int> ans;
  36
  37 struct node{
  38   node * left, * right;
  39   bool end;
  40   node(bool e) : end(e) {
  41     left = right = NULL;
  42   }
  43 };
  44
  45 void clean(node * n){
  46   if (n == NULL) return;
  47   clean(n->left); clean(n->right);
  48   delete n;
  49 }
  50
  51
  52 Int f(string s, node * n){
  53   Int left = 0, right = 0;
  54   if (n->left != NULL){
  55     left = f(s + "0", n->left);
  56   }
  57   if (n->right != NULL){
  58     right = f(s + "1", n->right);
  59   }
  60   if (n->end){
  61     Int x = ((1ULL) << (M - s.size())) - 1;
  62     if (M == 64 && s.size() == 0){
  63       x = ~(0ULL);
  64     }
  65     ans[s] = x - left - right + 1;
  66     //D(s); D(n->end);
  67     //D(ans[s]);
  68   }
  69   Int ret = 0;
  70   if (n->end){
  71     ret = ans[s];
  72   }
  73   return ret + left + right;
  74 }
  75
  76 int main(){
  77   int n;
  78   while (cin >> n >> M && !(n == 0 && M == 0)){
  79     ans.clear();
  80     node * root = new node(true);
  81     while (n--){
  82       string buf;
  83       cin >> buf;
  84       node * cur = root;
  85       for (int i=0; ; ++i){
  86         if (buf[i] == '*'){
  87           cur->end = true;
  88           break;
  89         }
  90         if (buf[i] == '0'){
  91           if (cur->left == NULL) cur->left = new node(false);
  92           cur = cur->left;
  93         }else{
  94           if (cur->right == NULL) cur->right = new node(false);
  95           cur = cur->right;
  96         }
  97       }
  98     }
  99
 100     f("", root);
 101
 102     int K;
 103     cin >> K;
 104     while (K--){
 105       string buf;
 106       cin >> buf;
 107       buf.resize(buf.size()-1);
 108       Int t = ans[buf];
 109       cout << t << endl;
 110     }
 111
 112     puts(" ");
 113   }
 114   return 0;
 115 }